package com.ly.algorithm.DataStructures.problem;



import java.util.Arrays;

/**
 * @Classname Floyd
 * @Description TODO
 * @Date 2020/5/5 11:39
 * @Author 冷心影翼
 */
public class Floyd {

    public static void main(String[] args) {
        char[] data = {'A','B','C','D','E','F','G'};
        Graph4 graph = new Graph4(data);
        graph.insertVerxs(0,0,0);
        graph.insertVerxs(1,1,0);
        graph.insertVerxs(2,2,0);
        graph.insertVerxs(3,3,0);
        graph.insertVerxs(4,4,0);
        graph.insertVerxs(5,5,0);
        graph.insertVerxs(6,6,0);
        graph.insertVerxs(0,1,5);
        graph.insertVerxs(0,2,7);
        graph.insertVerxs(0,6,2);
        graph.insertVerxs(1,3,9);
        graph.insertVerxs(1,6,3);
        graph.insertVerxs(2,4,8);
        graph.insertVerxs(3,5,4);
        graph.insertVerxs(4,6,4);
        graph.insertVerxs(4,5,5);
        graph.insertVerxs(5,6,6);
        graph.showGraph();
        graph.floyd();
        graph.showGraph();
    }
}



class Graph4 {
    private char[] vertex;
    private int[][] dis;
    private int[][] pre;

    public Graph4(char[] vertex) {
        this.vertex = vertex;
        dis = new int [vertex.length][vertex.length];
        pre = new int [vertex.length][vertex.length];
        final int N = 65535;
        for (int[] r: dis) {
            Arrays.fill(r,N);
        }
        for (int i=0;i<pre.length;i++) {
            Arrays.fill(pre[i],i);
        }
    }

    public void insertVerxs(int i, int j, int w) {
        dis[i][j] = w;
        dis[j][i] = w;
    }

    public void showGraph() {
        for(int[] r:dis) {
            System.out.println(Arrays.toString(r));
        }
//        for(int[] r:pre) {
//            System.out.println(Arrays.toString(r));
//        }
    }

    public void floyd() {
        int len = 0;
        for(int k=0;k<dis.length;k++) {
            for (int i=0;i<dis.length;i++) {
                for(int j=0;j<dis.length;j++) {
                    len = dis[i][k] + dis[k][j];
                    if(len < dis[i][j]) {
                        dis[i][j] = len;
                        pre[i][j] = pre[k][j];
                    }
                }
            }
        }
    }
}